package pfq.demo.algorithm.search;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 二分查找算法:
 * 1. 先将所要查找的序列从小到大进行排序
 * 2. 取出中间的数，将排好序的序列一分为二
 * 3. 与所要查找的数进行比较，如果大，则说明所要查找的数在此数的前半段，否则在后半段
 * 4. 最后再以此半段为整体序列，重新取出中间的数进行比较，如此这般直到找到为止
 */
public class BinarySearch {
    public static void main(String[] args) {

        List<Integer> data = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            data.add(i + 1);
        }

        // 使用Java自带的二分查找api
        int searchData = 5;
        int index = Collections.binarySearch(data, searchData);

        System.out.println("Collections.binarySearch: " + index);
        System.out.println("pangfq.binarySearch: " + binarySearch(data, searchData));

    }

    static int binarySearch(List<Integer> source, int searchData) {
        if (source != null && !source.isEmpty()) {
            int low = 0;
            int high = source.size() - 1;

            while (low < high) {
                // 向上取整
                int middleIndex = (int) Math.ceil((low + high) / 2.0);
                int middleData = source.get(middleIndex);
                if (searchData < middleData) {
                    high = middleIndex;
                } else if (searchData > middleData) {
                    low = middleIndex;
                } else {
                    return middleIndex;
                }

            }
        }

        return -1;
    }
}
